package com.example.design.leetcode.list;

//剑指 Offer 24. 反转链表
//    定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
//
//    示例:
//    输入: 1->2->3->4->5->NULL
//    输出: 5->4->3->2->1->NULL
//
//    限制：
//    0 <= 节点个数 <= 5000
//
//
//    注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

public class Practice29 {

    public static ListNode reverseList(ListNode head) {
        ListNode cur = null;
        ListNode pre = head;

        while(pre != null) {
            ListNode tmp = pre.next;
            pre.next = cur;
            cur = pre;
            pre = tmp;
        }

        return cur;
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode listNode = new ListNode(2);
        ListNode listNode1 = new ListNode(3);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(5);

        head.next = listNode;
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;

        ListNode listNode4 = reverseList2(head);
        System.out.println();
    }

    public static ListNode reverseList2(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;

        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    // 使用递归
    // 1、第一递归函数功能
//    public static ListNode reverseList3(ListNode head) {
//    }
    // 2,递归出口，设置n为很小，当n为0或为1时，直接返回head
    // 3,递归表达式
    // 这个的等价关系不像 n 是个数值那样，比较容易寻找。
    // 但是，它的递归表达式，一定是范围不断在缩小，对于链表来说，就是链表的节点个数不断在变小
    // 所以，如果你实在找不出，你就先对 reverseList(head.next) 递归走一遍，看看结果是咋样的
    public static ListNode reverseList3(ListNode head) {
        // 定义出口
        if (head == null || head.next == null) {
            return head;
        }

        // 实在找不出，你就先对 reverseList(head.next) 递归走一遍，看看结果是咋样的
        // 我们先把递归的结果保存起来，先不返回，因为我们还不清楚这样递归是对还是错。
        ListNode listNode = reverseList3(head.next);
        ListNode tmp = head.next;
        tmp.next = head;
        head.next = null;
        return listNode;
    }
}
